package com.zk.algorithm.dynamicprogramming;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Finished;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.annotation.Medium;

import java.util.Arrays;

/**
 * 测试不通过：
 *
 * [186,419,83,408]
 * 6249
 *
 * 这道题并不是优先选取 coin 最大的 (贪婪算法)，就行了
 *
 */
@Medium
@LeetCodeExplore
@Finished(false)
public class CoinChange {

    public static void main(String...args) {
        CoinChange coinChange = new CoinChange();
        int ans = coinChange.coinChangeGreedy(new int[] {
                186,419,83,408
        }, 6249);

        Utils.println(ans);
    }

    public int coinChangeGreedy(int[] coins, int amount) {
        Arrays.sort(coins);

        int i = coins.length - 1;
        int ans = 0;

        while (i >= 0) {
            int count = amount / coins[i];

            if (count != 0) {
                ans += count;
                amount -= coins[i] * count;
            }

            i--;
        }

        return (amount == 0) ? ans : -1;
    }

}
